We present an analytical method for computing the mean cover time of a randomwalk process on arbitrary, complex networks. The cover time is defined as thetime a random walker requires to visit every node in the network at least once.This quantity is particularly important for random search processes and targetlocalization in network topologies. Based on the global mean first passage timeof target nodes we derive an estimate for the cumulative distribution functionof the cover time based on first passage time statistics. We show that ourresult can be applied to various model networks, including Erd\H{o}s-R\'enyiand Barab\'asi-Albert networks, as well as various real-world networks. Ourresults reveal an intimate link between first passage and cover time statisticsin networks in which structurally induced temporal correlations decay quicklyand offer a computationally efficient way for estimating cover times in networkrelated applications.
展开▼
机译:我们提出一种分析方法,用于计算任意复杂网络上随机游走过程的平均覆盖时间。覆盖时间定义为随机步行者至少需要访问网络中每个节点一次的时间。此数量对于网络拓扑中的随机搜索过程和目标定位特别重要。基于目标节点的全局平均首次通过时间,我们根据首次通过时间统计数据得出覆盖时间累积分布函数的估计值。我们证明了我们的结果可以应用于各种模型网络,包括Erd \ H {o} s-R \'enyi和Barab \'asi-Albert网络,以及各种现实网络。我们的结果揭示了网络中首次通过和覆盖时间统计之间的紧密联系,其中结构性时间相关性迅速衰减,并提供了一种计算有效的方式来估算网络相关应用中的覆盖时间。
展开▼